package com.zyk.grate_offer.class01;

/**
 * 给定一个二维数组matrix，
 * 你可以从任何位置出发，走向上下左右四个方向
 * 返回能走出来的最长的递增链长度
 *
 * @author zhangsan
 * @date 2021/4/21 10:36
 */
public class Code05_LongestIncreasingPath {

    // 暴力尝试
    public static int longestIncreasingPath(int[][] matrix) {
        int R = matrix.length;
        int C = matrix[0].length;
        int ans = 0;
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                ans = Math.max(ans, process(matrix, r, c));
        return ans;
    }

    public static int process(int[][] m, int r, int c) {
        int up = (r > 0 && m[r - 1][c] > m[r][c]) ? process(m, r - 1, c) : 0;
        int down = (r < m.length - 1 && m[r + 1][c] > m[r][c]) ? process(m, r + 1, c) : 0;
        int left = (c > 0 && m[r][c - 1] > m[r][c]) ? process(m, r, c - 1) : 0;
        int right = (c < m[0].length - 1 && m[r][c + 1] > m[r][c]) ? process(m, r, c + 1) : 0;
        return Math.max(Math.max(left, right), Math.max(up, down)) + 1;
    }

    // 记忆话搜索
    public static int longestIncreasingPath2(int[][] matrix) {
        int R = matrix.length;
        int C = matrix[0].length;
        int ans = 0;
        int[][] dp = new int[R][C];
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                ans = Math.max(ans, process2(matrix, r, c, dp));
        return ans;
    }

    public static int process2(int[][] m, int r, int c, int[][] dp) {
        if(dp[r][c] != 0) return dp[r][c];
        int up = (r > 0 && m[r - 1][c] > m[r][c]) ? process2(m, r - 1, c, dp) : 0;
        int down = (r < m.length - 1 && m[r + 1][c] > m[r][c]) ? process2(m, r + 1, c, dp) : 0;
        int left = (c > 0 && m[r][c - 1] > m[r][c]) ? process2(m, r, c - 1, dp) : 0;
        int right = (c < m[0].length - 1 && m[r][c + 1] > m[r][c]) ? process2(m, r, c + 1, dp) : 0;
        int ans = Math.max(Math.max(left, right), Math.max(up, down)) + 1;
        dp[r][c] = ans;
        return ans;
    }


    // for test
    public static void main(String[] args) {
        int[][] matrix = {
                {1, 2,   3, 4},
                {8, 7,   6, 5},
                {9, 10,  11, 12},
                {1, 232, 231, 23},
        };
        System.out.println(longestIncreasingPath(matrix));
        System.out.println(longestIncreasingPath2(matrix));
    }

}
